// https://leetcode.cn/problems/move-zeroes/

// 题干:给定一个数组 nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。
// 请注意,必须在不复制数组的情况下原地对数组进行操作。

// 示例：输入: nums = [0,1,0,3,12]
//       输出: [1,3,12,0,0]

// 碎语：运用了双指针的算法，注意是快慢指针还是对撞指针
//       快慢指针一般用于环形链表和数组，本题中"数组分两块"一般就采用双指针来解决
//       根据本题，让遍历指针cur扫一遍数组，让prev指针指向非零元素的最后一位

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    void  moveZeroes(vector<int>& nums)
    {
        for(int cur = 0, prev = -1 ; cur < nums.size() ; cur++){
            if (nums[cur]){
                swap(nums[cur], nums[++prev]);
            }
        }
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,0,3,4,0,5};

    sol.moveZeroes(nums);

    for (auto num : nums){
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
